package myutil.mylist;

import java.util.Iterator;

/**
 * Doubly-linked list implementation of the {@code MyList}, 
 * {@code MyQueue} and {@code MyStack} interfaces.  
 * Permits all elements (including {@code null}).
 *
 * @author Hlib_Babii
 * @see     MyList
 * @see     MyArrayList
 * @since 1.0
 * @param <T> the type of elements held in this collection
 */
public class MyLinkedList<T> implements MyList<T>, MyStack<T>, MyQueue<T> {
    
    private static class Node<T> {
        private T value;
        private Node<T> prev;
        private Node<T> next;
        
        public Node(T value, Node<T> prev, Node<T> next) {
            this.value = value;
            this.prev = prev;
            this.next = next;
        }
    }

    /**
     * pointer to the first node
     */
    private Node<T> first;
   
    /**
     * pointer to the last node
     */
    private Node<T> last;
   
    /**
     * the number of nodes in the list
     */
    private int size;
   
    /**
     * constructs empty list
     */
    public MyLinkedList() {
    }
    
    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public MyLinkedList(MyList c) {
        addAll((T[]) c.toArray());
    }

    /**
     * returns iterator that iterates over MyLinkedList
     * @return iterator that iterates over MyLinkedList
     */
    @Override
    public Iterator<T> iterator() {
        return new MyIterator();
    }
    
    /**
     * inserts element to the beginning of the list
     * @param e element to be inserted
     */
    public void addFirst(T e) {
         insertToBeginning(e);
    }
   
    /**
     * inserts element to the end of the list
     * @param e element to be inserted
     */
    public void addLast(T e) {
        insertToEnd(e);
    }
    
    /**
     * returns the first element of this list
     * @return the first element of this list
     * @throws MyNoSuchElementException if the list is empty
     */
    public T getFirst() {
        final Node<T> node = first;
        if (node != null) {
            return node.value;
        } else {
            throw new MyNoSuchElementException();
        }
    }
 
    /**
     * returns the last element of this list
     * @return the last element of this list
     * @throws MyNoSuchElementException if the list is empty
     */
    public T getLast() {
        final Node<T> node = last;
        if (node != null) {
            return node.value;
        } else {
            throw new MyNoSuchElementException();
        }
    }
    
    /**
     * returns and removes the first element of this list
     * @return the first element of this list
     * @throws MyNoSuchElementException if the list is empty
     */
    public T removeFirst() {
        if (size() == 0) {
            throw new MyNoSuchElementException();
        }
        return unlinkFirst();
    }
    
    /**
     * returns and removes the last element of this list
     * @return the last element of this list
     * @throws MyNoSuchElementException if the list is empty
     */
    public T removeLast() {
        if (size() == 0) {
            throw new MyNoSuchElementException();
        }
        return unlinkLast();
    }
    
    /**
     * returns the iterator that iterates over this list in reverse order
     * @return the iterator that iterates over this list in reverse order
     */
    public Iterator<T> descendingIterator() //- извлекает итератор в обратном направлении
    {
        return new MyDescendingIterator();
    }

    /**
     * Appends the specified element to the end of this list.
     *
     * <p>This method is equivalent to {@link #addLast}.
     * @param e element to be appended
     */
    @Override
    public void add(T e) {
        insertToEnd(e);
    }

    /**
     * insert the specified element before the element with index {@code index}
     * @param index the index of the element before which the specified element 
     * will be inserted 
     * @param e element to be inserted
     */
    @Override
    public void add(int index, T e) {
        if (index == 0) {
            insertToBeginning(e);
        } else {
            final Node<T> nodeToInsertAfter = getNodeByIndex(index - 1);
            insertAfter(e, nodeToInsertAfter);
        };
    }

    /**
     * Appends all of the elements in the specified array to the end of
     * this list, in the same order as they are in the array.
     *
     * @param c array containing elements to be added to this list
     * @throws NullPointerException if the specified array is null
     */
    @Override
    public void addAll(T[] c) {
        addAll(size(), c);
    }

    
     /**
     * Inserts all of the elements in the specified array into this
     * list, starting at the specified position.  Shifts the element
     * currently at that position (if any) and any subsequent elements to
     * the right (increases their indices).  The new elements will appear
     * in the list in the order they are in the array.
     *
     * @param index index at which to insert the first element
     *              from the specified array
     * @param c array containing elements to be added to this list
     * @throws MyIndexOutOfBoundsException {@inheritDoc}
     * @throws NullPointerException if the specified array is null
     */
    @Override
    public void addAll(int index, T[] c) {
        if (c.length == 0) {
            return;
        }
        
        Node<T> after;
        Node<T> before;
        if (index == size) {
            after = null;
            before = last;
        } else {
            after = getNodeByIndex(index);
            before = after.next; 
        }
        Node<T> newNode = null;
        for (int i = 0; i < c.length; i++) {
            newNode = new Node(c[i], null, before);
            if (before == null) {
                first = newNode;
            } else {
                before.prev = newNode;
            }
            before = newNode;
        }
        
        if (after == null) {
            last = newNode;
        } else {
            after.next = newNode;
            newNode.prev = after;
        }
        
        size += c.length;
    }
    
    /**
     * Returns the element at the specified position in this list.
     *
     * @param index index of the element to return
     * @return the element at the specified position in this list
     * @throws MyIndexOutOfBoundsException {@inheritDoc}
     */
    @Override
    public T get(int index) {
        final Node<T> node = getNodeByIndex(index);
        return node.value;
    }

     /**
     * Removes the element at the specified position in this list.  Shifts any
     * subsequent elements to the left (subtracts one from their indices).
     * Returns the element that was removed from the list.
     *
     * @param index the index of the element to be removed
     * @return the element previously at the specified position
     * @throws MyIndexOutOfBoundsException {@inheritDoc}
     */
    @Override
    public T remove(int index) {
        final Node<T> node = getNodeByIndex(index);
        return unlink(node);
    }

    /**
     * removes all the elements from this list
     */
    @Override
    public void clear() {
        first = last = null;
        size = 0;
    }

    /**
     * checks whether list is empty
     * @return true if list is empty, false otherwise
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

     /**
     * Replaces the element at the specified position in this list with the
     * specified element.
     *
     * @param index index of the element to replace
     * @param element element to be stored at the specified position
     * @throws MyIndexOutOfBoundsException {@inheritDoc}
     */
    @Override
    public void set(int index, T e) {
        Node<T> node = getNodeByIndex(index);
        node.value = e;
    }

    /**
     * Returns the index of the first occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     *
     * @param o element to search for
     * @return the index of the first occurrence of the specified element in
     *         this list, or -1 if this list does not contain the element
     */
    @Override
    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<T> node = first; node != null; node = node.prev) {
                if (node.value == null) {
                    return index;
                }
                ++index;
            }
        } else {
            for (Node<T> node = first; node != null; node = node.prev) {
                if (o.equals(node.value)) {
                    return index;
                }
                ++index;
            }            
        }
        return -1;
    }

    /**
     * returns the number of elements in this list
     * @return the number of elements in this list
     */
    @Override
    public int size() {
        return size;
    }

     /**
     * Returns an array containing all of the elements in this list
     * in proper sequence (from first to last element).
     *
     * @return an array containing all of the elements in this list
     *         in proper sequence
     */
    @Override
    public Object[] toArray() {
        Object[] array = new Object[size];
        int index = 0;
        for (Node<T> node = first; node != null; node = node.prev) {
            array[index++] = node.value;
        }
        return array;
    }

    // MyStack
    
    /**
     * Pushes an element onto the stack represented by this list.  In other
     * words, inserts the element at the front of this list.
     *
     * <p>This method is equivalent to {@link #addFirst}.
     *
     * @param e the element to push 
     */
    @Override
    public void push(T e) {
        addFirst(e);
    }

    /**
     * Pops an element from the stack represented by this list.  In other
     * words, removes and returns the first element of this list.
     *
     * <p>This method is equivalent to {@link #removeFirst()}.
     *
     * @return the element at the front of this list (which is the top
     *         of the stack represented by this list)
     * @throws MyNoSuchElementException if this list is empty
     */
    @Override
    public T pop() {
        return removeFirst();
    }

    // MyQueue
    
     /**
     * Adds the specified element as the tail (last element) of this list.
     *
     * @param e the element to add
     */
    @Override
    public void offer(T e) {
        addLast(e);
    }

     /**
     * Retrieves, but does not remove, the head (first element) of this list.
     *
     * @return the head of this list, or {@code null} if this list is empty
     */
    @Override
    public T peek() {
        T res = null;
        try {
            res = getFirst();
        } catch (MyNoSuchElementException ex) {}
        return res;
    }

     /**
     * Retrieves and removes the head (first element) of this list.
     *
     * @return the head of this list, or {@code null} if this list is empty
     */
    @Override
    public T poll() {
        T res = null;
        try {
            res = removeFirst();
        } catch (MyNoSuchElementException ex) {}
        return res;
    }
    
    // private section
    
    /**
     * insert specified element to the end,
     * operates with nodes
     */
    private void insertToEnd(T e) {
        final Node<T> newLastNode  = new Node(e, null, last);
        if (first == null) {
            first = newLastNode;
        } else {
            last.prev = newLastNode;
        }
        last = newLastNode;
        ++size;
    }
    
    /**
     * removes the last element
     */
    private T unlinkLast() {
        return unlink(last);
    }
    
    /**
     * inserts the specified element to the beginning,
     * operates with nodes
     */
    private void insertToBeginning(T e) {
        final Node<T> newFirstNode  = new Node(e, first, null);
        if (last == null) {
            last = newFirstNode;
        } else {
            first.next = newFirstNode;
        }
        first = newFirstNode;
        ++size;
    }
    
    /**
     * removes the first element
     */
    private T unlinkFirst() {
        return unlink(first);
    }
    
    /**
     * inserts specified element after specified node,
     * operates with nodes
     */
    private void insertAfter(T e, Node<T> node) {
        assert node != null;
        
        final Node<T> nodeAfter = node.prev;
        final Node<T> newNode = new Node<T>(e, nodeAfter, node);
        node.prev = newNode;
        if (nodeAfter != null) {
            nodeAfter.next = newNode;
        } else {
            last = newNode;
        }
        ++size;
    }
    
    /**
     * removes specified node
     */
    private T unlink(Node<T> node) {
        // assert node != null;
        
        final Node<T> nodeToUnlink = node;
        final Node<T> nodeAfter = nodeToUnlink.prev;
        final Node<T> nodeBefore = nodeToUnlink.next;
        if (nodeBefore != null) {
            nodeBefore.prev = nodeAfter;
        } else {
            first = nodeAfter;
        }
        if (nodeAfter != null) {
            nodeAfter.next = nodeBefore;
        } else {
            last = nodeBefore;
        }
        --size;
        return nodeToUnlink.value;

    }
    
    /**
     * returns node by given index,
     * searches for it either from the beginning or from the end
     */
    private Node<T> getNodeByIndex(int index) {
        checkIndex(index);
        // find out where it is easier to reach a node 
        // from the first or from the last node
        Node<T> nodeToFind;
        if (size >> 1 > index) { // from the beginning
            nodeToFind = first;
            while (index > 0) {
                nodeToFind = nodeToFind.prev;
                --index;
            }
        } else {
            nodeToFind = last;
            while (index < size -1) {
                nodeToFind = nodeToFind.next;
                ++index;
            }
        }
        return nodeToFind;
    }    
    
    /*
     * checks weather index is within bounds
     */
    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new MyIndexOutOfBoundsException();
        }
    }
    
    class MyIterator implements Iterator<T> {
        
        protected Node<T> next;
        
        private Node<T> lastReturned = null;
        
        public MyIterator() {
            next = first;
        }

        @Override
        public boolean hasNext() {
            return next != null;
        }

        @Override
        public T next() {
            if (next != null) {
                lastReturned = next;
                next = getNextNode(next);
                return lastReturned.value;  
            } else {
                throw new MyNoSuchElementException();
            }
        }

        @Override
        public void remove() {
            if (lastReturned != null) {
                unlink(lastReturned);
                lastReturned = null;
            }
        }

        protected Node<T> getNextNode(Node<T> node) {
            return node.prev;
        }
    }
    
    class MyDescendingIterator extends MyIterator {
        
        public MyDescendingIterator() {
            next = last;
        }

        protected Node<T> getNextNode(Node<T> node) {
            return node.next;
        }
    }
}
